package Offer;
class BinaryTreeNode
{
	int value;
	BinaryTreeNode left;
	BinaryTreeNode right;
	BinaryTreeNode(int value)
	{
		this.value=value;
	}
}
public class Test18 
{

	public static void main(String[] args) 
	{
		

	}
    public static boolean hasSubtree(BinaryTreeNode root1,BinaryTreeNode root2)
    {
    	if(root1==null)
    		return false;
    	if(root2==null)
    	{
    		return true;
    	}
    	boolean result =false;
    	if(root1.value==root2.value)
    	{
    		result = doesTree1HasTree2(root1,root2);
    	}
    	
    	if(!result)
    	{
    		result = hasSubtree(root1.left,root2);
    	}
    	if(!result)
    	{
    		result = hasSubtree(root1.right,root2);
    	}
    	return result;
    }
    public static boolean doesTree1HasTree2(BinaryTreeNode root1,BinaryTreeNode root2)
    {
    	if(root1==null)
    		return false;
    	if(root2==null)
    		return true;
    	if(root1.value!=root2.value)
    	{
    		return false;
    	}
    	return doesTree1HasTree2(root1.left,root2.left)&&doesTree1HasTree2(root1.right,root2.right);
    }
          
    
}

class IsSubTree{
	 public static boolean hasSubTree(TreeNode list1, TreeNode list2){
		 boolean result = false;
		 if(list1 != null && list2 != null){
			 if(list1.value == list2.value){
				 result = doesTree1HasTree2(list1,list2);
			 }
			 if(!result){
				 result = hasSubTree(list1.left,list2);
			 }
			 if(!result){
				 result = hasSubTree(list1.right,list2);
			 } 
		 }
		 return result;
	 }
	 public static boolean doesTree1HasTree2(TreeNode list1, TreeNode list2){
		 if(list2 == null){
			 return true;
		 }
		 if(list1 == null){
			 return false;
		 }
		 if(list1.value != list2.value){
			 return false;
		 }
		 return doesTree1HasTree2(list1.left, list2.left) 
				 && doesTree1HasTree2(list1.right, list2.right);
	 }
}

